package personal.leil.learning.binary;


import personal.leil.learning.insert.InsertSort;
import personal.leil.learning.utils.ArrayUtils;

/**
 * 二分查找代码实现
 * <p>
 * 题目描述：
 * ① 在一个有序数组中查找到等于目标数的索引
 * ② 在一个有序数组中查找到等于目标数最左侧的索引
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2024-1-2
 */
public class BinarySearch {

    public static int binarySearch1(int[] arr, int target) {
        return process1(arr, target, 0, arr.length - 1);
    }

    /**
     * for ①
     *
     * @param arr    target array
     * @param target target number
     * @return result index (if not found, return -1)
     */
    public static int process1(int[] arr, int target, int L, int R) {
        if (L > R) {
            return -1;
        }
        if (R == L) {
            if (arr[L] == target) {
                return L;
            } else {
                return -1;
            }
        }
        int mid = L + ((R - L) >> 1);
        if (arr[mid] > target) {
            return process1(arr, target, L, mid - 1);
        } else if (arr[mid] < target) {
            return process1(arr, target, mid + 1, R);
        } else {
            return mid;
        }
    }

    public static int binarySearch2(int[] arr, int target) {
        return process2(arr, target, 0, arr.length - 1);
    }

    /**
     * for ②
     *
     * @param arr    target array
     * @param target target number
     * @return result index (if not found, return -1)
     */
    public static int process2(int[] arr, int target, int L, int R) {
        if (L > R) {
            return -1;
        }
        if (R == L) {
            if (arr[L] == target) {
                return L;
            } else {
                return -1;
            }
        }
        int mid = L + ((R - L) >> 1);
        if (arr[mid] >= target) {
            return process2(arr, target, L, mid);
        } else {
            return process2(arr, target, mid + 1, R);
        }
    }

    /********************* For Test *************************/

    public static void main(String[] args) {
        int[] arr = {34, 23, 43, 54, 234, 54, 2, 4, 564, 54, 6, 2, 342, 43, 4, 243, 43, 45, 333333, 42, 4};
        InsertSort.insertSort(arr);
        System.out.println("source array");
        ArrayUtils.printArr(arr);
        int target = 54;
        int index1 = binarySearch1(arr, target);
        System.out.println("target num index for ①: " + index1);
        int index2 = binarySearch2(arr, target);
        System.out.println("target num index for ②: " + index2);
    }

}
